Theory of Computation

By Prof. Raghunath Tewari | IIT Kanpur

Learners enrolled: 4479

This is an introductory course on Theory of Computation intended for undergraduate students in computer science. In this course we will introduce various models of computation and study their power and limitations. We will also explore the properties of the corresponding language classes defined by these models and the relations between them. We will assume the student is comfortable in analytical reasoning and has preferably done a course on Data Structures and Algorithms.

INTENDED AUDIENCE: Computer Science undergraduate students.

PRE-REQUISITES: It is recommended that the candidate has done a course in Data Structures and Algorithms.

INDUSTRY SUPPORT: Content will be updated soon

Summary

Course Status :	Completed
Course Type :	Elective
Language for course content :	English
Duration :	8 weeks
Category :	Computer Science and Engineering Foundations of Computing
Credit Points :	2
Level :	Undergraduate
Start Date :	26 Jul 2021
End Date :	17 Sep 2021
Enrollment Ends :	09 Aug 2021
Exam Date :	26 Sep 2021 IST

Note: This exam date is subject to change based on seat availability. You can check final exam date on your hall ticket.

Page Visits

Course layout

Week 1: Finite Automata – deterministic and nondeterministic, regular operations

Week 2: Regular Expression, Equivalence of DFA, NFA and REs, closure properties

Week 3: Non regular languages and pumping lemma, DFA Minimization,

Week 4: CFGs, Chomsky Normal Form

Week 5: Non CFLs and pumping lemma for CFLs, PDAs, Equivalence of PDA and CFG

Week 6: Properties of CFLs, DCFLs, Turing Machines and its variants

Week 7: Configuration graph, closure properties of decidable languages, decidability properties of regular languages and CFLs

Week 8: Undecidability, reductions, Rice's Theorem, introduction to complexity theory

Books and references

Introduction to the Theory of Computation by Michael Sipser

Instructor bio

Prof. Raghunath Tewari

IIT Kanpur

Raghunath Tewari is an Associate Professor in the department of Computer Science and Engineering at IIT Kanpur. His research interests lie in the areas of computational complexity theory, algorithms and graph theory.

Course certificate

The course is free to enroll and learn from. But if you want a certificate, you have to register and write the proctored exam conducted by us in person at any of the designated exam centres.
The exam is optional for a fee of Rs 1000/- (Rupees one thousand only).
Date and Time of Exams: 26 September 2021 Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
Registration url: Announcements will be made when the registration form is open for registrations.
The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published. If there are any changes, it will be mentioned then.
Please check the form for more details on the cities where the exams will be held, the conditions you agree to when you fill the form etc.

CRITERIA TO GET A CERTIFICATE

Average assignment score = 25% of average of best 6 assignments out of the total 8 assignments given in the course.
Exam score = 75% of the proctored certification exam score out of 100

Final score = Average assignment score + Exam score

YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.

Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IIT Kanpur .It will be e-verifiable at nptel.ac.in/noc.

Only the e-certificate will be made available. Hard copies will not be dispatched.

Once again, thanks for your interest in our online courses and certification. Happy learning.

- NPTEL team

SWAYAM Helpline / Support